package search_alg;

import java.util.ArrayList;

import city_model.City;
import city_model.Station;

public class YenAlg {
	
	public ArrayList<ArrayList<RouteNodeInformation>> YenSearch(Station start, Station goal, City city, int nr)
	{
		ArrayList<ArrayList<RouteNodeInformation>> paths = new ArrayList<ArrayList<RouteNodeInformation>>(nr);
		ArrayList<ArrayList<RouteNodeInformation>> potentialPaths = new ArrayList<ArrayList<RouteNodeInformation>>();
        ArrayList<RouteEdgeAvailability> routeEdgeAvailability = new ArrayList<RouteEdgeAvailability>();
        int nrOfPaths = nr-1;
        
		paths.add(0, new AStarAlg().AStarSearch(start, goal, city, routeEdgeAvailability));
		System.out.println("a");
		int k = 1;
//		for (int k = 1; k <= nrOfPaths; k++)
//		{
			for (int i = 1; i < paths.get(k-1).size()-1; i++)
			{
				RouteNodeInformation spurNode = paths.get(k-1).get(i);
				
				ArrayList<RouteNodeInformation> rootPath = new ArrayList<RouteNodeInformation>();
				for(int j = 0; j <= i; j++ )
				{
					rootPath.add(j, paths.get(k-1).get(j));
				}
				
				for (ArrayList<RouteNodeInformation> p : paths)
				{
					if(comparePaths(rootPath, p, i))
					{
						routeEdgeAvailability.add(new RouteEdgeAvailability(p.get(i).getNodeId(), p.get(i+1).getNodeId(), p.get(i+1).getTransportMode()));
					}
				}
							
				ArrayList<RouteNodeInformation> spurPath = new AStarAlg().AStarSearch(getStationById(start, goal, city, spurNode), goal, city, routeEdgeAvailability);
				System.out.println("c");
				ArrayList<RouteNodeInformation> tempPath = new ArrayList<RouteNodeInformation>();
				tempPath.addAll(rootPath);
				if (spurPath != null)
				{
					spurPath.remove(0);
					tempPath.addAll(spurPath);
					potentialPaths.add(tempPath);
				}
				
				routeEdgeAvailability.clear();
			}
			
			for (int p = 1; p <= nrOfPaths; p++)
			{
				if (potentialPaths.size() != 0)
				{
					ArrayList<RouteNodeInformation> shortestPath =  getShortestPath(potentialPaths);
					potentialPaths.remove(shortestPath);
					paths.add(p, shortestPath);
				}
			}
//		}
		return paths;
	}
	
	private boolean comparePaths(ArrayList<RouteNodeInformation> p1, ArrayList<RouteNodeInformation> p2, int size)
	{
		boolean result = true;
		for (int i = 0; i <= size; i++)
		{
			if (!p1.get(i).equals(p2.get(i)))
			{
				result = false;
			}
		}
		return result;
	}
	
	private int getPathCost(ArrayList<RouteNodeInformation> path)
	{
		int cost = 0;
		for (RouteNodeInformation node : path)
		{
			cost += node.getTime();
		}
		
		return cost;
	}
	
	private ArrayList<RouteNodeInformation> getShortestPath(ArrayList<ArrayList<RouteNodeInformation>> paths)
	{
		int min = Integer.MAX_VALUE;
		ArrayList<RouteNodeInformation> result = new ArrayList<RouteNodeInformation>();
		
		for (ArrayList<RouteNodeInformation> path : paths)
		{
			if (getPathCost(path) < min)
			{
				min = getPathCost(path);
				result = path;
			}
		}
		return result;
	}
	
	private Station getStationById(Station start, Station stop, City c, RouteNodeInformation nodeInfo)
	{
		if (nodeInfo.getNodeId().equals("0"))
		{
			return start;
		}
		else if (nodeInfo.getNodeId().equals("1"))
		{
			return stop;
		}
		else
		{
			return c.getStationById(nodeInfo.getNodeId());
		}
	}

}
